ต้นไม้ (Tree) เป็นโครงสร้างข้อมูลแบบชั้นเชิงที่ไม่เป็นเส้นตรง ซึ่งจำลองโครงสร้างองค์กรในโลกจริง เช่น ระบบไฟล์หรือต้นตระกูล ต่างจากลำดับแบบเส้นตรงของรายการ แสต็ค และคิว จุดสำคัญของต้นไม้อยู่ที่ความเป็นความเป็นชั้นเชิง (Hierarchical)และความเป็นแบบเรียกซ้ำ (Recursive)。
1. การวิเคราะห์รูปร่างของต้นไม้
- โหนด (Node): หน่วยพื้นฐานที่ประกอบด้วยคีย์ (Key) และข้อมูล (Payload)
- โหนดราก (Root): โหนดเดียวที่ไม่มีขอบเข้ามา ถือเป็นจุดเริ่มต้นของต้นไม้
- ขอบ (Edge): ทางเดินเดียวที่เชื่อมต่อโหนด แสดงความสัมพันธ์ระหว่างพ่อแม่และลูก
- โหนดใบ (Leaf): ปลายทางที่ไม่มีโหนดลูก ถือเป็นขอบเขตธรรมชาติที่ใช้หยุดกระบวนการเรียกซ้ำ
2. มุมมองสองด้านของการกำหนดแบบเรียกซ้ำ
เราสามารถเข้าใจต้นไม้ได้จากมุมมองสองแบบ:
มุมมองด้านภาพวาด
กราฟที่ไม่มีวงจรและเชื่อมต่อกัน ประกอบด้วยโหนดและขอบ โดยแต่ละโหนด (ยกเว้นราก) จะมีพ่อแม่เพียงโหนดเดียวเท่านั้น
กราฟที่ไม่มีวงจรและเชื่อมต่อกัน ประกอบด้วยโหนดและขอบ โดยแต่ละโหนด (ยกเว้นราก) จะมีพ่อแม่เพียงโหนดเดียวเท่านั้น
มุมมองแบบเรียกซ้ำ
ต้นไม้จะว่างเปล่า หรือประกอบด้วยโหนดรากและต้นไม้ย่อย (Subtree) จำนวนหนึ่งหรือมากกว่า
ต้นไม้จะว่างเปล่า หรือประกอบด้วยโหนดรากและต้นไม้ย่อย (Subtree) จำนวนหนึ่งหรือมากกว่า
ตัวอย่างต้นไม้โครงสร้างเอกสาร HTML DOM
ใน HTML
<html> เป็นโหนดราก<body> และ <head> เป็นโหนดพี่น้อง แท็กแต่ละอันและเนื้อหาที่ซ้อนกันเป็นต้นไม้ย่อยร่วมกัน โครงสร้างนี้ทำให้เราสามารถย้ายกลุ่ม <ul> และทุก <li> โดยไม่ทำลายลำดับชั้นภายใน